package Homework;

import com.sun.deploy.panel.JreTableModel;

public class DoubleLinked{
    private Node head;
    private Node tail;
    private int size;
    private Node dummyHead;

    public DoubleLinked(){
        this.dummyHead=new Node(-1);
    }

   public void addFirst(int val){
        Node node=new Node(null,val,head);
        if(head==null){
            //此时链表为空
            tail=node;
        }else{
            //此时链表不为空
            head.prev=node;
        }
       //不论何时node都是head
        head=node;
        size++;
   }

   public void addLast(int value){
        Node node=new Node(tail,value,null);
        if(head==null){
            //此时链表为空
            head=node;
        }else{
            //此时链表不为空
            tail.next=node;
        }
        //不论何时node都是tail
        tail=node;
        size++;
   }

   public void addIndex(int index ,int value){
        //1.判断index的合法性————不能使用函数
       if(index<0||index>size){
           //index不合法
           System.err.println("get index illegal!");
           return;
       }else if(index==0){
           addFirst(value);
       }else if(index==size){
           addLast(value);
       }else{
           //此时既不是头节点，也不是尾结点，需要找到它的前驱和后继————抽象称为方法
           Node prev=findNode(index-1);
           Node node=new Node(prev,value,prev.next);
           prev.next=node;
           prev.next.prev=node;
       }
   }

    /**
     * 根据index值返回对应的val
     * @param index
     * @return
     */
   public int  getByIndex(int index){
       //1，判断index的合法性
       if(rangeIndex(index)){
           return findNode(index).val;
       }else {
           System.err.println("get index illegal!");
           return -1;
       }
   }

   public boolean contains(int value){
       for (Node node=head;node!=null ; node=node.next) {
           if(node.val==value){
               return true;
           }
       }
       return false;
   }

    /**
     * 将index位置的value改为newValue，并且返回Value
     * @param index
     * @param newValue
     * @return
     */
   public int set(int index ,int newValue){
       if(rangeIndex(index)){
           Node node=findNode(index);
           int oldVal =node.val;
           node.val=newValue;
           return oldVal;
       }else{
           System.err.println("get index illegal!");
           return -1;
       }
   }

    /**
     * 删除指定位置（index处）的节点
     * @param index
     */
   public void removeIndex(int index){
       if(rangeIndex(index)){
           Node node=findNode(index);
           unlink(node);
       }else {
           System.err.println("Get index illegal!");
           return;
       }
   }
   public void removeFirst(){
       removeIndex(0);
   }
   public void removeLast(){
       removeIndex(size-1);
   }

    /**
     * 删除第一个值为value的节点
     * @param value
     */
    public void removeValueOnce(int value) {
        for(Node x=head;x!=null;x=x.next){
            if(x.val==value){
                unlink(x);
                return;
            }
        }
    }

    /**
     * 删除值为value的所有节点
     * @param value
     */
    public void removeValueAll(int value){
        for(Node x=head;x!=null;){
            if(x.val==value){
                Node next=x.next;
                unlink(x);
                x=next;
            }else{
                x=x.next;
            }
        }
    }

    /**
     * 删除某一特定（node）节点
     * @param node
     */
    private void unlink(Node node) {
       //分治思想
       Node prev=node.prev;
       Node next=node.next;
       //先处理前半边情况
       if(prev==null){
           //此时node为头节点
           head=next;
       }else{
           //此时node存在前驱
           node.prev=null;
           prev.next=next;
       }
        //再处理后半边情况
       if(next==null){
           //此时node为尾节点
           prev=tail;
       }else{
           //此时node存在前驱后继
           node.next=null;
           node.prev=prev;
       }
       size--;
    }

    private boolean rangeIndex(int index){
       if(index<0||index>=size){
           return false;
       }else {
           return true;
       }
   }
   private Node findNode(int index){
        Node ret=null;
        if(index<(size>>1)){
            //index在前半部分
            ret=head;
            for (int i = 0; i <size ; i++) {
                ret=ret.next;
            }
        }else {
            ret=tail;
            for (int i = size-1; i >index; i--) {
                ret=ret.prev;
            }
        }
        return ret;
   }
   public String toString(){
        String ret="";
        for(Node x=head;x!=null;x=x.next){
            ret+=x.val;
            ret+="->";
        }
        ret+=null;
        return ret;
   }
}

 class Node {
    Node prev;
    int val;
    Node next;

    public Node(){};
    public Node(int val){
        this.val=val;
    }
    public Node(Node prev, int val,Node next){
        this.prev=prev;
        this.val=val;
        this.next=next;
    }
}


